# LeetCode 860、柠檬水找零

# 一、题目描述

在柠檬水摊上,每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品,(按账单 bills 支付的顺序)一次购买一杯。

每位顾客只买一杯柠檬水,然后向你付 5 美元、10 美元或 20 美元。

你必须给每个顾客正确找零,也就是说净交易是每位顾客向你支付 5 美元。

注意,一开始你手头没有任何零钱。

给你一个整数数组 bills ,其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零,返回 true ,否则返回 false 。

# 二、题目解析

# 三、参考代码

# 1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 柠檬水找零( LeetCode 860 ):https://leetcode-cn.com/problems/lemonade-change/
class Solution {
    public boolean lemonadeChange(int[] bills) {
        
        // 用来记录 5 元钞票的数量
        int five = 0;

        // 用来记录 10 元钞票的数量
        int ten = 0;

        // 顾客开始按顺序购买,并找零
        for(int i = 0 ; i < bills.length ; i++){
            // 1、如果发现是 5 元面额
            if(bills[i] == 5){
                // 那么可以直接收钱,不需要找零
                // 并且 5 元钞票的数量加 1
                five++;

                // 2、如果发现是 10 元面额
            }else if(bills[i] == 10){

                // 如果手中有 5 元钞票,则找零 5 元
                if(five > 0){
                    // 5 元钞票的数量减 1
                    five--;
                    // 10 元钞票的数量加 1
                    ten++;
                }else{
                    // 如果手中没有 5 元钞票,说明找零失败
                    return false;
                }

                // 3、如果发现是 20 元面额
            }else{

                // 如果手中有 10 元 和 5 元钞票,则找零 1 张 10 元和 1 张 5 元的钞票
                if(ten > 0 && five > 0){
                    // 5 元钞票的数量减 1
                    five--;
                    // 10 元钞票的数量减 1
                    ten--;
                }else{
                    // 如果手中只有 5 元的,并且数量超过或者等于 3 张
                    // 那么找零 3 张 5 元的钞票
                    if(five >= 3){
                        // 5 元钞票的数量减 3
                        five -= 3;
                    }else{
                        // 说明这个时候顾客付 20 元的时候
                        // 1、手中没有 1 张 10 元的和 1 张 5 元的
                        // 2、手中没有 3 张 5 元的
                        // 说明找零失败
                        return false;
                    }
                }
            }
        }
        // 所有顾客都找零了,成功
        return true;
    }
}

# **2、**C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 柠檬水找零( LeetCode 860 ):https://leetcode-cn.com/problems/lemonade-change/
class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
         // 用来记录 5 元钞票的数量
        int five = 0;

        // 用来记录 10 元钞票的数量
        int ten = 0;

        // 顾客开始按顺序购买,并找零
        for(int i = 0 ; i < bills.size() ; i++){
            // 1、如果发现是 5 元面额
            if(bills[i] == 5){
                // 那么可以直接收钱,不需要找零
                // 并且 5 元钞票的数量加 1
                five++;

                // 2、如果发现是 10 元面额
            }else if(bills[i] == 10){

                // 如果手中有 5 元钞票,则找零 5 元
                if(five > 0){
                    // 5 元钞票的数量减 1
                    five--;
                    // 10 元钞票的数量加 1
                    ten++;
                }else{
                    // 如果手中没有 5 元钞票,说明找零失败
                    return false;
                }

                // 3、如果发现是 20 元面额
            }else{

                // 如果手中有 10 元 和 5 元钞票,则找零 1 张 10 元和 1 张 5 元的钞票
                if(ten > 0 && five > 0){
                    // 5 元钞票的数量减 1
                    five--;
                    // 10 元钞票的数量减 1
                    ten--;
                }else{
                    // 如果手中只有 5 元的,并且数量超过或者等于 3 张
                    // 那么找零 3 张 5 元的钞票
                    if(five >= 3){
                        // 5 元钞票的数量减 3
                        five -= 3;
                    }else{
                        // 说明这个时候顾客付 20 元的时候
                        // 1、手中没有 1 张 10 元的和 1 张 5 元的
                        // 2、手中没有 3 张 5 元的
                        // 说明找零失败
                        return false;
                    }
                }
            }
        }
        // 所有顾客都找零了,成功
        return true;
    }
};

# 3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https:#www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 柠檬水找零( LeetCode 860 ):https:#leetcode-cn.com/problems/lemonade-change/
class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        # 用来记录 5 元钞票的数量
        five = 0

        # 用来记录 10 元钞票的数量
        ten = 0

        # 顾客开始按顺序购买,并找零
        for i  in range(len(bills)) : 
            # 1、如果发现是 5 元面额
            if bills[i] == 5 :
                # 那么可以直接收钱,不需要找零
                # 并且 5 元钞票的数量加 1
                five += 1

                # 2、如果发现是 10 元面额
            elif bills[i] == 10 :

                # 如果手中有 5 元钞票,则找零 5 元
                if five > 0 :
                    # 5 元钞票的数量减 1
                    five -= 1
                    # 10 元钞票的数量加 1
                    ten += 1
                else : 
                    # 如果手中没有 5 元钞票,说明找零失败
                    return False
    
                # 3、如果发现是 20 元面额
            else : 

                # 如果手中有 10 元 和 5 元钞票,则找零 1 张 10 元和 1 张 5 元的钞票
                if ten > 0 and five > 0 :
                    # 5 元钞票的数量减 1
                    five -= 1
                    # 10 元钞票的数量减 1
                    ten -= 1
                else:
                    # 如果手中只有 5 元的,并且数量超过或者等于 3 张
                    # 那么找零 3 张 5 元的钞票
                    if five >= 3 : 
                        # 5 元钞票的数量减 3
                        five -= 3
                    else :
                        # 说明这个时候顾客付 20 元的时候
                        # 1、手中没有 1 张 10 元的和 1 张 5 元的
                        # 2、手中没有 3 张 5 元的
                        # 说明找零失败
                        return False

        # 所有顾客都找零了,成功
        return True

# 四、复杂度分析

时间复杂度:O(N),其中 N 是 bills 的长度。

空间复杂度:O(1)。